
//675.为高尔夫比赛砍树
class Solution {
public:
    int cutOffTree(vector<vector<int>>& forest) {
        //进行模拟
        //使用BFS,其中BFS的起点是在改变的
        int n=forest.size(),m=forest[0].size();
        int dx[]={0,0,1,-1};
        int dy[]={1,-1,0,0};
        priority_queue<vector<int>,vector<vector<int>>,greater<vector<int>>> pq;  //对树的高度进行排序,带上坐标
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++)
                if(forest[i][j]>1) pq.push({forest[i][j],i,j}); 



        int xi=0,yi=0,tar_x,tar_y,ret=0;
        function<int(int,int)> bfs=[&](int _x,int _y)  //进行BFS,从一个位置找最小位置需要的步数
        {
            vector<vector<int>> vist(n,vector<int>(m));
            vist[_x][_y]=1;
            queue<pair<int,int>> q;
            q.push({_x,_y});
            int step=0;
            while(!q.empty())
            {
                int _size=q.size();
                for(int i=0;i<_size;i++)
                {
                    int x=q.front().first,y=q.front().second;
                    q.pop();
                    if(x==tar_x&&y==tar_y) return step;
                    for(int k=0;k<4;k++)
                    {
                        int a=x+dx[k],b=y+dy[k];
                        if(a>=0&&a<n&&b>=0&&b<m&&forest[a][b]&&!vist[a][b])
                        {   
                            vist[a][b]=1;
                            q.push({a,b});
                        }   
                    }
                }
                step++;
            }
            return -1;
        };

        while(pq.size())
        {
            auto tmp=pq.top();
            pq.pop();
            tar_x=tmp[1],tar_y=tmp[2];
            int step=bfs(xi,yi);     //求需要多少步走到最小树的位置
            if(step==-1) return -1;
            else ret+=step;
            xi=tar_x,yi=tar_y;  //记录下一次走的起始位置
        }
        return ret;
    }
};